#include <bits/stdc++.h>

using namespace std;

// class Solution { // O(nM^2)
//     public:
//         int longestValidSubstring(string word, vector<string>& forbidden) {
//             int n = word.size(), ans = 0;
//             unordered_set<string> dic(forbidden.begin(), forbidden.end());
//             int left = 0;
//             for(int right = 0; right < n; ++right){
//                 for(int m = 1; m <= min(10, right - left + 1); ++m){
//                     if(dic.count(word.substr(right - m + 1, m))){
//                         left = right - m + 2;
//                         break;
//                     }
//                 }
//                 ans = max(ans, right - left + 1);
//             }
//             return ans;
//         }
//     };

const int inf = 0x3f3f3f3f;
const int N = 1e6 + 10;

int sz, ch[N][26];
int f[N], min_len[N];

void init(){
    sz = 1;
    memset(ch[0], 0, sizeof(ch[0]));
    min_len[0] = inf;
}

void add(string &s){
    int u = 0, c = 0;
    int len = s.length();
    for(int i=0; i<len; ++i){
        c = s[i] - 'a';
        if(!ch[u][c]){
            memset(ch[sz], 0, sizeof(ch[sz]));
            min_len[sz] = inf;
            ch[u][c] = sz++;
        }
        u = ch[u][c];
    }
    min_len[u] = min(min_len[u], len);
}

void getfail(){
    queue<int> Q;
    f[0] = 0;
    for(int c=0; c<26; ++c){
        int u = ch[0][c];
        if(u){
            f[u] = 0;
            Q.push(u);
        }
    }
    while(!Q.empty()){
        int r = Q.front(); Q.pop();
        for(int c=0; c<26; ++c){
            int u = ch[r][c];
            if(!u){
                ch[r][c] = ch[f[r]][c];
                continue;
            }
            Q.push(u);
            int v = f[r];
            while(v && !ch[v][c])   v = f[v];
            f[u] = ch[v][c];
            min_len[u] = min(min_len[u], min_len[f[u]]);
        }
    }
}


// 作者：Hongrock
// 链接：https://leetcode.cn/problems/length-of-the-longest-valid-substring/solutions/2345818/aczi-dong-ji-onjie-fa-wu-shi-chang-du-10-47dy/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { // ac 自动机
public:
    int longestValidSubstring(string s, vector<string>& forbidden) {
        init();
        for(auto &s : forbidden)    add(s);
        getfail();
        int n = s.length();
        int cur = 0;
        int ans = 0;
        int u = 0;
        for(int i=0; i<n; ++i){
            u = ch[u][s[i] - 'a'];
            cur = max(cur, i - min_len[u] + 2);
            ans = max(ans, i - cur + 1);
        }
        return ans;
    }
};

int main() {
    
    //system("pause");
    return 0;
}
